#include "01_knapsack.h"

knapsack::knapsack(const int &total, const int &capacity, const int *profits, const int *weights)
{
    this->total = total;
    this->capacity = capacity;
    this->profits = new int[this->total];
    this->weights = new int[this->total];
    this->solution = new int[this->total];
    for (int i = 0; i < this->total; i++)
    {
        this->profits[i] = profits[i];
        this->weights[i] = weights[i];
        this->solution[i] = 0;
    }
    this->optimum = NAN;
}

knapsack::~knapsack()
{
    delete[] this->profits;
    delete[] this->weights;
    delete[] this->solution;
}

void knapsack::dp()
{
    /* init the memo */
    int row = this->total + 1, column = this->capacity + 1;
    int *temp = new int[row * column];
    int (*memo)[column] = (int (*)[column])temp;
    memset(memo, 0, row * column);

    /* bottom up dynamic programming */
    int i, c;
    for (i = this->total - 1; i >= 0; i--)
        for (c = 0; c <= this->capacity; c++)
        {
            if (c < this->weights[i])
                memo[i][c] = memo[i + 1][c];
            else
                memo[i][c] = max(memo[i + 1][c], memo[i + 1][c - this->weights[i]] + this->profits[i]);
        }

    /* calculate the optimum */
    i++, c--;
    this->optimum = memo[i][c];

    /* backtracking to find the solution vector */
    for ( ; i < this->total - 1; i++)
    {
        int now = memo[i][c];
        int next = memo[i + 1][c];
        if (now != next)
        {
            this->solution[i] = 1;
            c -= this->weights[i];
        }
        else
            this->solution[i] = 0;
    }
    this->solution[i] = memo[i][c] ? 1 : 0;
}

void knapsack::dfs()
{
    int sum_of_profits = 0;
    for (int i = 0; i < this->total; i++)
        sum_of_profits += this->profits[i];

    node init(this->solution, sum_of_profits, 0, 0, this->total);
    dfs(init);
}

void knapsack::bfs()
{
    int sum_of_profits = 0;
    for (int i = 0; i < this->total; i++)
        sum_of_profits += this->profits[i];

    queue<node> buf;
    node init(this->solution, sum_of_profits, 0, 0, this->total);
    buf.push(init);

    while (buf.size())
    {
        node now(NULL, NAN, NAN, NAN, NAN);
        now = buf.front();
        buf.pop();

        if (now.profit < this->optimum)
            continue;
        if (now.step == this->total)
        {
            this->optimum = now.profit;
            for (int i = 0; i < this->total; i++)
                this->solution[i] = now.solution[i];
            continue;
        }

        for (int i = 1; i >= 0; i--)
        {
            node next(NULL, NAN, NAN, NAN, NAN);
            switch (i)
            {
            case 1:
                if (now.weight + this->weights[now.step] <= this->capacity)
                {
                    next = now;
                    next.solution[next.step] = 1;
                    next.weight += this->weights[next.step];
                    next.step++;
                    buf.push(next);
                }
                break;
            case 0:
                next = now;
                next.profit -= this->profits[next.step];
                next.step++;
                buf.push(next);
                break;
            default:
                break;
            }
        }
    }
}

int knapsack::get_optimum()
{
    return this->optimum;
}

int *knapsack::get_solution()
{
    return this->solution;
}

void knapsack::dfs(node &now)
{
    if (now.profit < this->optimum)
        return;
    if (now.step == this->total)
    {
        this->optimum = now.profit;
        for (int i = 0; i < this->total; i++)
            this->solution[i] = now.solution[i];
        return;
    }

    for (int i = 1; i >= 0; i--)
    {
        node next(NULL, NAN, NAN, NAN, NAN);
        switch (i)
        {
        case 1:
            if (now.weight + this->weights[now.step] <= this->capacity)
            {
                next = now;
                next.solution[next.step] = 1;
                next.weight += this->weights[next.step];
                next.step++;
                dfs(next);
            }
            break;
        case 0:
            next = now;
            next.profit -= this->profits[next.step];
            next.step++;
            dfs(next);
            break;
        default:
            break;
        }
    }
}